package office;

/**
 * 第一轮整体遍历，求出a^b（因为相同的数字异或为0，0异或任何数字为数字自身）
 * 然后结合a^b以及原来数组求出这两个数字
 *      原理：用一个只有一位为1的数字来遍历异或整个数组，把这个数组分成两个子数组（异或结果相同的数字在同一个子数组），
 *      如果是两个相同的数字，它们一定在同一个子数组里（保证子数组异或时为0），现在只需要把两个只出现一次的数字分到不同
 *      的子数组，那么子数组分别遍历异或得到的两个数字就是这两个数字。
 * 怎么把两个只出现一次的数字分到不同地子数组？
 *      找到a^b第一个为1的位置，异或结果为1说明a和b在这一位上不同，那用只有这一位为1的数字m去分别异或a和b，得到的结果一
 *      定不同，也就把a和b分到了不同的子数组。结合上一点得出结果。
 */
public class Offer56_1_singleNumbers {
    public int[] singleNumbers(int[] nums) {
        int x = 0, y = 0, m = 1, i = 0;
        for (int num : nums) {
            i ^= num;
        }
        while ((i & m) == 0) {
            m <<= 1;
        }
        for (int num : nums) {
            if ((m & num) == 0) {
                x ^= num;
            } else {
                y ^= num;
            }
        }
        return new int[]{x, y};
    }
}
